8788. Монеты

 

У Вас имеется бесконечное количество монет номиналами от 1 до n. Вы хотите выбрать некоторый набор монет суммой s. Разрешено иметь в наборе монеты с одинаковым номиналом. Какое минимальное количество монет необходимо взять, чтобы набрать сумму s.

 

Вход. Два целых чисел n и s (1 ≤ n ≤ 105, 1 ≤ s ≤ 109).

 

Выход. Выведите минимальное количество монет, необходимое для взятия суммы s.

 

Пример входа 1

Пример выхода 1

5 11

3

 

 

Пример входа 2

Пример выхода 2

6 16

3

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

Если s > n, то выгодно брать монету номиналом n. Берем наибольшее количество k монет номиналом n, для которого s ≥ k * n. Если остаток s – k * n больше 0, то используем еще одну монету. Таким образом ответ равен s / n плюс одна монета если s не делится на n нацело.

 

Пример

В первом примере берем 11 / 5 = 2 монеты наибольшего номинала n = 5. Остаток 11 – 2 * 5 = 1 больше нуля, поэтому следует взять еще одну монету номиналом 1.

 

Реализация алгоритма

Читаем входные данные.

 

scanf("%d %d", &n, &s);

 

Вычисляем и выводим ответ.

 

res = s / n;

if (s % n > 0) res++;

printf("%d\n", res);

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int s = con.nextInt();

    int res = s / n;

    if(s % n > 0) res++;

    System.out.println(res);

    con.close();

  }

}

 

Python реализация

 

n, s = map(int, input().split())

res = s // n

if s % n > 0: res += 1

print(res)